Incentive analysis: Nakamoto PoW

Mining in Game theory

Aggelos Kiayias et al. FC'16

Models Bitcoin mining as a game, where nodes decide on which blocks to extend and whether to release a mined block.

For small players controlling less than 1/3 of the resources, following Bitcoin’s protocol specification is a Nash equilibrium.

Assumption: All honest miners can communicate with 0 latency, and the adversary cannot perform form any network level attacks (such as rushing).

Juan Beccuti, Christian Jaag (Swiss Economics Working Paper 0060)

Consider a game in which Bitcoin miners compete for a reward of each solved puzzle in a sequence of them.

model it as a sequential game with imperfect information, in which miners have to choose whether or not to report their success.

Show that the game has a multiplicity of equilibria and we analyze the parameter constellations for each of them.

In particular, the minimum requirement to find it optimal not to report is decreasing with the number of miners who are not reporting, and increasing the heterogeneity among players reduces the likelihood that they choose not to report

Nikos Leonardos, Stefanos Leonardos, and Georgios Piliouras

Best paper at MARBLE'19

Yujin Kwon, Hyoungshick Kim, Jinwoo Shin, Yongdae Kim (KAIST)

Monash University, CSIRO-Data61

Show rational participants to launch 51% attacks in two cases.

1. Attacking another blockchain w/ compatible mining algorithms

2. Renting mining power from cloud mining services.

Formally model profit-driven malicious behaviours as a series of actions through a Markov Decision Process.

Result: for most mainstream PoW-based blockchains, ,51% attacks are feasible and profitable

Investigate the recent 51% attack on Ethereum Classic (Jan. 2019)

Discouragement

Michael Mirkin, Yan Ji, Jonathan Pang, Ariah Klages-Mundt, Ittay Eyal and Ari Juels

CCS'20

RPD framework

Christian Badertscher, Juan Garay, Ueli Maurer, Daniel Tschudi, and Vassilis Zikas

Selfish mining

Ittay Eyal and Emin G¨un Sirer (Cornell University)

FC'14

Rational miners will prefer to join the selfish miners, and the colluding group will increase in size until it becomes a majority.

Ayelet Sapirshtein, Yonatan Sompolinsky, and Aviv Zohar (The Hebrew University of Jerusalem)

FC'15

Concurrent to and independent of our work, Sapirshtein et al. also observe that selfish mining is suboptimal. They define a broad strategy space and use a combination of analytic bounds and numeric solvers to compute approximately-optimal strategies from this space. Their strategy space is a generalization of our stubborn mining strategies; however, they do not consider how to compose mining attacks with eclipse attack

Fault tolerance in uncoordinated majority model: ~0.2321

Kartik Nayak, Srijan Kumar, Andrew Miller (University of Maryland) and Elaine Shi

S&P'16

Kevin Alarcón Negy (Cornell University), Peter R. Rizun (Bitcoin Unlimited), Emin Gün Sirer (Cornell University)

FC'20

Intermittent selfish mining: Against difficulty adjustment

Show its profittability per time unit

Rafael Pass, Elaine Shi (Cornell Tech / Cornell Uni)

In our model where the adversary can control the delivery of messages, the bitcoin protocol is not incentive compatible even for players controlling less than a 1/3 of the computational resources—there is a selfish mining attack which enables an attacker to gain 1/2 of the block rewards

Ethereum

Fabian Ritz, Alf Zugenmaier

EuroS&PW'18

Cyril Grunspan, Ricardo Pérez-Marco

ICDCS'19

Bribing

Patrick McCorry, et al.

Present three smart contracts that allow a briber to fairly exchange bribes to miners who pursue a mining strategy benefiting the briber

Selling private keys to attackers

Kevin Liao (Arizona State University), Jonathan Katz

FC'17

Joseph Bonneau (Stanford University)

BitcoinW'16

Bribing for censorship on transactions

Rewards

Miles Carlsten (Princeton)

Hasu, James Prestwich, Brandon Curtis, October 2019

Xi Chen, Christos Papadimitriou, Tim Roughgarden (Columbia University)

SBC'20

Mining pool

Meni Rosenfeld

Overview of reward distribution

Pool hopping, Sabotage, Lie in wait and their workarounds

Raulo

Pool Hopping Attack

Lear Bahack

Difficulty Raising Attack, Block Discarding Attack

Nicolas T. Courtois, Lear Bahack

Overview of miner's attack and Block Withholding Attack

Ittay Eyal

Define and analyze a game where pools use some of their participants to infiltrate other pools and perform such an attack.

With any number of pools, no-pool-attacks is not a Nash equilibrium.

With two pools, or any number of identical pools, there exists an equilibrium that constitutes a tragedy of the commons where the pools attack one another and all earn less than they would have if none had attacked.

For two pools, the decision whether or not to attack is the miner’s dilemma, an instance of the iterative prisoner’s dilemma.

Yujin Kwon, Dohyun Kim, Yunmok Son, Eugene Vasserman, Yongdae Kim

Fork Afer Withholding (FAW) Attacks